The first iteration of Dijkstra's algorithm processes the source node 'A', finalizing its distance and relaxing its immediate neighbors.

  • The algorithm pops (0, 'A') from the Priority Queue, confirming that the shortest path to A is 0.
  • Node A is immediately marked as visited, meaning its shortest distance is finalized.
  • We examine neighbor B: the path through A is $0 + w(A, B) = 1$. Since $1 < \infty$, we update $d[B]=1$ and push (1, 'B') to the PQ.
  • We examine neighbor C: the path through A is $0 + w(A, C) = 4$. Since $4 < \infty$, we update $d[C]=4$ and push (4, 'C') to the PQ.
  • The Priority Queue now contains two entries: [(1, 'B'), (4, 'C')], with 'B' having the lowest cost.
Current State: Distances and Predecessors